#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>


typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;

struct ListNode* Buysltnode(int n)
{
    struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (tmp == NULL)
    {
        perror("malloc Buysltnode");
        exit(-1);
    }
    tmp->val = n;
    tmp->next = NULL;
    return tmp;
}

struct ListNode* Creatlist(int n, int arr[20])
{
    struct ListNode* front = NULL;
    struct ListNode* tmp = NULL;
    int i = 0;
    for (i = 0; i < n; i++)
    {
        struct ListNode* new = Buysltnode(arr[i]);
        if (new == NULL)
        {
            perror("malloc Buysltnode");
            exit(-1);
        }
        if (front == NULL)
        {
            front = new;
            tmp = new;
        }
        else
        {
            tmp->next = new;
            tmp = tmp->next;
        }
    }
    return front;
}

void SLTprint(struct ListNode* head)
{
    struct ListNode* tmp = head;
    while (tmp)
    {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
}



ListNode* partition(ListNode* pHead, int x) 
{
        // write code here
        ListNode* cmpmin = NULL;
        ListNode* newcmpmin = NULL;
        ListNode* cmpmax = NULL;
        ListNode* newcmpmax = NULL;
        ListNode* tmp = pHead;
        while (tmp)
        {
            if (tmp->val < x)
            {
                if (cmpmin == NULL)
                {
                    cmpmin = newcmpmin = tmp;
                    tmp = tmp->next;
                }
                else
                {
                    cmpmin->next = tmp;
                    cmpmin = cmpmin->next;
                    tmp = tmp->next;
                }
            }
            else
            {
                if (cmpmax == NULL)
                {
                    cmpmax = newcmpmax = tmp;
                    tmp = tmp->next;
                }
                else
                {
                    cmpmax->next = tmp;
                    cmpmax = cmpmax->next;
                    tmp = tmp->next;
                }
            }
        }
        if (cmpmax)
        {
            cmpmax->next = NULL;
        }
        if (cmpmin != NULL)
        {
            cmpmin->next = newcmpmax;
        }
        if (cmpmin == NULL)
        {
            return newcmpmax;
        }
        return newcmpmin;
};

int main()
{
    int arr1[20] = { 3,3,3 };
    int arr2[20] = { 1,3,4 };
    struct ListNode* new1 = Creatlist(3, arr1);
    SLTprint(new1);
    struct ListNode* p1 = partition(new1, 3);
    SLTprint(p1);
    return 0;
}